import java.util.*;
public class Text2 {
    //第二题  ： 腐烂的苹果   算法 ： 深搜
    boolean[][] flg;
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型ArrayList<ArrayList<>>
     * @return int整型
     */
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        // write code here
        int a = grid.size();
        int b = grid.get(0).size();
        flg = new boolean[a][b];
        //要一个队列  装坏掉的苹果
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < a; i++) {
            for(int j = 0; j < b;j++) {
                if(grid.get(i).get(j) == 2) {
                    queue.offer(new int[]{i,j});
                }
            }
        }
        int time =0;  //记录时间
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int[] arr = queue.poll();
                int t1 = arr[0];
                int t2 = arr[1];

                for(int k = 0; k < 4;k++) {
                    int x = t1 + dx[k];
                    int y = t2 + dy[k];

                    if(x >= 0 && x < a && y >= 0 && y<b &&grid.get(x).get(y) == 1 && flg[x][y] == false) {
                        //开始感染
                        flg[x][y] = true;
                        queue.offer(new int[]{x,y});
                    }
                }
            }
            time++;
        }
        for(int i = 0;i < a;i++) {
            for(int j = 0; j< b; j++) {
                if(grid.get(i).get(j) == 1 && flg[i][j] == false) {
                    return -1;
                }
            }
        }
        return time -1;
    }
}
